---
id: unit5
title: 笔试题
---

##

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 有效括号组合需满足：左括号必须以正确的顺序闭合。

示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：
输入：n = 1 输出：["()"]

### 方法 1

分析： - 必须以左括号开始 - 右括号数量等于左括号数量 - 每个位置要么是左括号，要么是右括号，n 对括号，2n 个字符，共有 2 的 2n 次幂种可能 - 每个位置生成左括号或者右括号，可以使用递归

先处理字符串是否是合理的组合，设置计数变量，遇到左括号 +1，遇到右括号 -1。过程中，计数为负就不是合理组合，最终结果为 0 就是合理组合。

```js
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
  var valid = function (str) {
    let count = 0;
    for (let i = 0; i < str.length; i++) {
      if (str[i] === "(") {
        count++;
      } else {
        count--;
      }

      if (count < 0) {
        return false;
      }
    }

    return count === 0;
  };

  var allStr = function (cur, n, strArr) {
    if (cur.length === n) {
      if (valid(cur)) {
        strArr.push(cur);
      }
      return cur;
    }

    cur += "(";
    cur = allStr(cur, n, strArr);
    cur = cur.slice(0, cur.length - 1);
    cur += ")";
    cur = allStr(cur, n, strArr);
    cur = cur.slice(0, cur.length - 1);
    return cur;
  };

  let arr = [];
  let str = "";
  allStr(str, n * 2, arr);
  return arr;
};
```

### 方法 2
- 如果左括号数量小于n，那么可以放一个左括号，如果有括号数量小于左括号，可以放一个右括号。

```js
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  var backtrack = function (strArr, cur, left, right, n) {
    if (cur.length === 2 * n) {
      strArr.push(cur);
      return cur;
    }

    if (left < n) {
      cur += '(';
      cur = backtrack(strArr, cur, left + 1, right, n);
      cur = cur.slice(0, cur.length - 1);
    }

    if (right < left) {
      cur += ')';
      cur = backtrack(strArr, cur, left, right + 1, n);
      cur = cur.slice(0, cur.length - 1);
    }
    return cur;
  }

  let arr = [];
  let str = '';
  backtrack(arr, str, 0, 0, n);
  return arr;
};

```
